package main

import (
	"fmt"
	"time"
)

// 官方解体思路
// func isValid(s string) bool {
//     n := len(s)
//     if n % 2 == 1 {
//         return false
//     }
//     pairs := map[byte]byte{
//         ')': '(',
//         ']': '[',
//         '}': '{',
//     }
//     stack := []byte{}
//     for i := 0; i < n; i++ {
//         if pairs[s[i]] > 0 {
//             if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
//                 return false
//             }
//             stack = stack[:len(stack)-1]
//         } else {
//             stack = append(stack, s[i])
//         }
//     }
//     return len(stack) == 0
// }

var bottom = []string{}

func push(c string) {
	bottom = append(bottom, c)
}

func pop() string {
	num := len(bottom)
	result := "-1"
	if num != 0 {
		result = bottom[num-1]
		bottom = bottom[0 : num-1]
	} else {
		// fmt.Println("empty")
		return result
	}
	return result
}

func isValid(s string) bool {
	//堆
	left := []string{"{", "[", "("}
	right := []string{"}", "]", ")"}
	num := len(s)
	flag := 0
	var popstring string

	for i := 0; i < num; i++ {
		compare := (string)(s[i])
		// 判断是否为左边括号,是的话入栈
		for j := 0; j < 3; j++ {
			if compare == left[j] {
				// fmt.Println(compare)
				push(compare)
				flag++
			}

			if compare == right[j] {
				popstring = pop()
				// fmt.Println(compare)
				if popstring == "-1" || popstring != left[j] {
					return false
				}
				flag--
			}

		}

	}
	if flag == 0 {
		return true
	} else {
		return false
	}
}

func main() {
	start := time.Now()
	s := "){"
	dec := isValid(s)
	cost := time.Since(start)
	fmt.Println(dec)
	fmt.Println(cost)
}
